package arithmetic.LeetCode;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
 * 322. 零钱兑换
 * 相关企业
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 *
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 *
 * @author jiangfeng on 2023/12/22
 */
public class CoinChange {
    public static void main(String[] args) {
        System.out.println(new Solution().coinChange(new int[]{1,2,5},11));
         System.out.println(new Solution().coinChange(new int[]{186,419,83,408},6249));
         System.out.println(new Solution().coinChange(new int[]{2,3,5},54));
    }

    static class Solution{
        // 记忆搜索法
        public int coinChange(int[] coins, int amount) {
            //int
            return 0;
        }
        public int coin(int[] coins, int res,int[] count){
            return 0;
        }
    }
    static class Solution3{
        // 想象成走楼梯的进阶版 动态规划问题
        public int coinChange(int[] coins, int amount) {
            if(amount==0){
                return 0;
            }
            // dp[i] = dp[i-1] + min{}
            // dp[i] 表示到达楼梯第i层所需要的最少步数，可以走coins数组里的步数
            int[] dp = new int[amount+1];
            Arrays.fill(dp,Integer.MAX_VALUE);
            dp[0]=0;
            Arrays.sort(coins);
            for(int i=0;i<coins.length;i++){
                for(int j = coins[i];j<=amount;j++){
                    //更新当前金额的最小兑换次数
                    if(dp[j-coins[i]]==Integer.MAX_VALUE){
                        continue;
                    }
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
            if(dp[amount]==Integer.MAX_VALUE){
                return -1;
            }
            return  dp[amount];

        }
    }
    static class Solution2
    {
        public int coinChange(int[] coins, int amount) {
            if(amount==0){
                return 0;
            }
            //动态规划 , 回溯

            Arrays.sort(coins);
            for(int i=coins.length-1;i>=0;i--) {
                // 回溯，不要最大的那个。
                int result = 0;
                int total= 0;
                while (i >= 0) {
                    total += coins[i];
                    result++;
                    if (total == amount) {
                        return result;
                    }
                    // 比他大则
                    if (total > amount) {
                        total -= coins[i];
                        i--;
                        result--;
                    }
                }
            }

            return -1;
        }
    }
}
